#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums, int k)
    {
        int n = nums.size();
        int f = 0, res = 0;
        for (int i = 0; i < k * n; i++)
        {
            f = max(f, 0) + nums[i % n];
            res = max(res, f);
        }
        return res;
    }

    int kConcatenationMaxSum(vector<int>& arr, int k) {
        if (k == 1)  return maxSubArray(arr, 1);
        int mod = 1e9 + 7;
        long long res = maxSubArray(arr, 2);
        int s = reduce(arr.begin(), arr.end());
        res += 1LL * max(s, 0) * (k - 2);
        return res % mod;
    }
};